package com.techyuan.algorithm.leetcode;

/**
 * 迷宫类问题可以使用DFS（深度优先搜索）算法
 * Created by tianjuntao on 2016/12/8.
 */
public class CountBattleships {
    /**
     * 思路：
     * 只找表示船头的元素个数
     * 这种思路利用了船只能在水平方向或是垂直方向上延伸，因此船的最左边（水平方向）或是最上边（垂直方向）的元素就很特殊，因为它的左边（水平方向）或是上边（垂直方向）的元素会是’.’，而对于船中部的元素，它们的左边或是上边的元素肯定有一个会是’X’。
     * 利用这点，我们可以遍历矩阵每一个元素，当符合是船头元素时，就增加船的个数，否则继续遍历下一个元素，最后返回找到的船的个数即可。
     * @param board
     * @return
     */
    static int countBattleships(char[][] board) {
        if (board.length == 0)
            return 0;

        int rsize = board.length;
        int csize = board[0].length;
        int count = 0;

        for (int i = 0; i < rsize; i++)
            for (int j = 0; j < csize; j++)
                if (board[i][j] == 'X' && (i == 0 || board[i - 1][j] == '.') && (j == 0 || board[i][j - 1] == '.'))
                    count++;

        return count;
    }

    public static void main(String[] args) {
        //char[][] board = new char[][]{new char[]{'X', '.', '.', 'X'}, new char[]{'.', '.', '.', 'X'}, new char[]{'.', '.', '.', 'X'}};
        char[][] board = new char[][]{new char[]{'.', '.', '.', 'X'}, new char[]{'X', 'X', 'X', 'X'}, new char[]{'.', '.', '.', 'X'}};
        System.out.println(countBattleships(board));
    }
}
